package bst

import (
	"bytes"
	"fmt"
	"go-guide/utils/intefaces"
)

type BST struct {
	root *node
	size uint32
}

type node struct {
	left  *node
	right *node
	val   interface{}
}

func NewBST() *BST {
	return &BST{
		root: nil,
		size: 0,
	}
}

func (b *BST) Size() uint32 {
	return b.size
}

func (b *BST) Empty() bool {
	return b.size == 0
}

func (b *BST) Add(e interface{}) {
	b.root = b.add(b.root, e)
}

func (b *BST) PreOrder() {
	preOrder(b.root)
}

// 是否包含某一个元素
func (b *BST) Contains(e interface{}) bool {
	return contain(b.root, e)
}

func contain(n *node, e interface{}) bool {
	if n == nil {
		return false
	}

	if intefaces.Compare(e, n.val) == 0 {
		return true
	}
	return contain(n.left, e) || contain(n.right, e)
}

func (b *BST) String() string {
	var buffer bytes.Buffer
	generateBSTSting(b.root, 0, &buffer)
	return buffer.String()
}

/** ---- private method ----- */

func (b *BST) add(n *node, e interface{}) *node {
	// 如果根节点为空的话
	if n == nil {
		b.size++
		return &node{
			left:  nil,
			val:   e,
			right: nil,
		}
	}
	if intefaces.Compare(e, n.val) > 0 {
		n.right = b.add(n.right, e)
	} else {
		n.left = b.add(n.left, e)
	}
	return n
}

func preOrder(n *node) {
	if n == nil {
		return
	}
	preOrder(n.left)
	fmt.Println(n.val)
	preOrder(n.right)
}

// 生成以 Node 为根节点，深度为 depth 的描述二叉树的字符串
func generateBSTSting(n *node, depth int, buffer *bytes.Buffer) {
	if n == nil {
		buffer.WriteString(generateDepthString(depth) + "nil\n")
		return
	}

	buffer.WriteString(generateDepthString(depth) + fmt.Sprint(n.val) + "\n")
	generateBSTSting(n.left, depth+1, buffer)
	generateBSTSting(n.right, depth+1, buffer)
}

func generateDepthString(depth int) string {
	var buffer bytes.Buffer
	for i := 0; i < depth; i++ {
		buffer.WriteString("--")
	}
	return buffer.String()
}
